
<!DOCTYPE html>

<html class="no-js" lang="zh">
<head>
<meta charset="utf-8"/>
<meta content="width=device-width,initial-scale=1" name="viewport"/>
<link href="../../../assets/images/favicon.png" rel="icon"/>
<meta content="mkdocs-1.4.2, mkdocs-material-8.5.9" name="generator"/>
<title>队列 - 玉子的笔记本</title>
<link href="../../../assets/stylesheets/main.20d9efc8.min.css" rel="stylesheet"/>
<link href="../../../assets/stylesheets/palette.08040f6c.min.css" rel="stylesheet"/>
<style>:root{--md-admonition-icon--note:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M2.5 7.775V2.75a.25.25 0 0 1 .25-.25h5.025a.25.25 0 0 1 .177.073l6.25 6.25a.25.25 0 0 1 0 .354l-5.025 5.025a.25.25 0 0 1-.354 0l-6.25-6.25a.25.25 0 0 1-.073-.177zm-1.5 0V2.75C1 1.784 1.784 1 2.75 1h5.025c.464 0 .91.184 1.238.513l6.25 6.25a1.75 1.75 0 0 1 0 2.474l-5.026 5.026a1.75 1.75 0 0 1-2.474 0l-6.25-6.25A1.75 1.75 0 0 1 1 7.775zM6 5a1 1 0 1 0 0 2 1 1 0 0 0 0-2z"/></svg>');--md-admonition-icon--abstract:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M2.5 1.75a.25.25 0 0 1 .25-.25h8.5a.25.25 0 0 1 .25.25v7.736a.75.75 0 1 0 1.5 0V1.75A1.75 1.75 0 0 0 11.25 0h-8.5A1.75 1.75 0 0 0 1 1.75v11.5c0 .966.784 1.75 1.75 1.75h3.17a.75.75 0 0 0 0-1.5H2.75a.25.25 0 0 1-.25-.25V1.75zM4.75 4a.75.75 0 0 0 0 1.5h4.5a.75.75 0 0 0 0-1.5h-4.5zM4 7.75A.75.75 0 0 1 4.75 7h2a.75.75 0 0 1 0 1.5h-2A.75.75 0 0 1 4 7.75zm11.774 3.537a.75.75 0 0 0-1.048-1.074L10.7 14.145 9.281 12.72a.75.75 0 0 0-1.062 1.058l1.943 1.95a.75.75 0 0 0 1.055.008l4.557-4.45z"/></svg>');--md-admonition-icon--info:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M8 1.5a6.5 6.5 0 1 0 0 13 6.5 6.5 0 0 0 0-13zM0 8a8 8 0 1 1 16 0A8 8 0 0 1 0 8zm6.5-.25A.75.75 0 0 1 7.25 7h1a.75.75 0 0 1 .75.75v2.75h.25a.75.75 0 0 1 0 1.5h-2a.75.75 0 0 1 0-1.5h.25v-2h-.25a.75.75 0 0 1-.75-.75zM8 6a1 1 0 1 0 0-2 1 1 0 0 0 0 2z"/></svg>');--md-admonition-icon--tip:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M3.499.75a.75.75 0 0 1 1.5 0v.996C5.9 2.903 6.793 3.65 7.662 4.376l.24.202c-.036-.694.055-1.422.426-2.163C9.1.873 10.794-.045 12.622.26 14.408.558 16 1.94 16 4.25c0 1.278-.954 2.575-2.44 2.734l.146.508.065.22c.203.701.412 1.455.476 2.226.142 1.707-.4 3.03-1.487 3.898C11.714 14.671 10.27 15 8.75 15h-6a.75.75 0 0 1 0-1.5h1.376a4.489 4.489 0 0 1-.563-1.191 3.833 3.833 0 0 1-.05-2.063 4.636 4.636 0 0 1-2.025-.293.75.75 0 1 1 .525-1.406c1.357.507 2.376-.006 2.698-.318l.009-.01a.748.748 0 0 1 1.06 0 .75.75 0 0 1-.012 1.074c-.912.92-.992 1.835-.768 2.586.221.74.745 1.337 1.196 1.621H8.75c1.343 0 2.398-.296 3.074-.836.635-.507 1.036-1.31.928-2.602-.05-.603-.216-1.224-.422-1.93l-.064-.221c-.12-.407-.246-.84-.353-1.29a2.404 2.404 0 0 1-.507-.441 3.063 3.063 0 0 1-.633-1.248.75.75 0 0 1 1.455-.364c.046.185.144.436.31.627.146.168.353.305.712.305.738 0 1.25-.615 1.25-1.25 0-1.47-.95-2.315-2.123-2.51-1.172-.196-2.227.387-2.706 1.345-.46.92-.27 1.774.019 3.062l.042.19a.753.753 0 0 1 .01.05c.348.443.666.949.94 1.553a.75.75 0 1 1-1.365.62c-.553-1.217-1.32-1.94-2.3-2.768a85.08 85.08 0 0 0-.317-.265c-.814-.68-1.75-1.462-2.692-2.619a3.74 3.74 0 0 0-1.023.88c-.406.495-.663 1.036-.722 1.508.116.122.306.21.591.239.388.038.797-.06 1.032-.19a.75.75 0 0 1 .728 1.31c-.515.287-1.23.439-1.906.373-.682-.067-1.473-.38-1.879-1.193L.75 5.677V5.5c0-.984.48-1.94 1.077-2.664.46-.559 1.05-1.055 1.673-1.353V.75z"/></svg>');--md-admonition-icon--success:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M13.78 4.22a.75.75 0 0 1 0 1.06l-7.25 7.25a.75.75 0 0 1-1.06 0L2.22 9.28a.75.75 0 0 1 1.06-1.06L6 10.94l6.72-6.72a.75.75 0 0 1 1.06 0z"/></svg>');--md-admonition-icon--question:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M8 1.5a6.5 6.5 0 1 0 0 13 6.5 6.5 0 0 0 0-13zM0 8a8 8 0 1 1 16 0A8 8 0 0 1 0 8zm9 3a1 1 0 1 1-2 0 1 1 0 0 1 2 0zM6.92 6.085c.081-.16.19-.299.34-.398.145-.097.371-.187.74-.187.28 0 .553.087.738.225A.613.613 0 0 1 9 6.25c0 .177-.04.264-.077.318a.956.956 0 0 1-.277.245c-.076.051-.158.1-.258.161l-.007.004a7.728 7.728 0 0 0-.313.195 2.416 2.416 0 0 0-.692.661.75.75 0 0 0 1.248.832.956.956 0 0 1 .276-.245 6.3 6.3 0 0 1 .26-.16l.006-.004c.093-.057.204-.123.313-.195.222-.149.487-.355.692-.662.214-.32.329-.702.329-1.15 0-.76-.36-1.348-.863-1.725A2.76 2.76 0 0 0 8 4c-.631 0-1.155.16-1.572.438-.413.276-.68.638-.849.977a.75.75 0 1 0 1.342.67z"/></svg>');--md-admonition-icon--warning:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M8.22 1.754a.25.25 0 0 0-.44 0L1.698 13.132a.25.25 0 0 0 .22.368h12.164a.25.25 0 0 0 .22-.368L8.22 1.754zm-1.763-.707c.659-1.234 2.427-1.234 3.086 0l6.082 11.378A1.75 1.75 0 0 1 14.082 15H1.918a1.75 1.75 0 0 1-1.543-2.575L6.457 1.047zM9 11a1 1 0 1 1-2 0 1 1 0 0 1 2 0zm-.25-5.25a.75.75 0 0 0-1.5 0v2.5a.75.75 0 0 0 1.5 0v-2.5z"/></svg>');--md-admonition-icon--failure:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M3.404 12.596a6.5 6.5 0 1 1 9.192-9.192 6.5 6.5 0 0 1-9.192 9.192zM2.344 2.343a8 8 0 1 0 11.313 11.314A8 8 0 0 0 2.343 2.343zM6.03 4.97a.75.75 0 0 0-1.06 1.06L6.94 8 4.97 9.97a.75.75 0 1 0 1.06 1.06L8 9.06l1.97 1.97a.75.75 0 1 0 1.06-1.06L9.06 8l1.97-1.97a.75.75 0 1 0-1.06-1.06L8 6.94 6.03 4.97z"/></svg>');--md-admonition-icon--danger:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M10.561 1.5a.016.016 0 0 0-.01.004L3.286 8.571A.25.25 0 0 0 3.462 9H6.75a.75.75 0 0 1 .694 1.034l-1.713 4.188 6.982-6.793A.25.25 0 0 0 12.538 7H9.25a.75.75 0 0 1-.683-1.06l2.008-4.418.003-.006a.02.02 0 0 0-.004-.009.02.02 0 0 0-.006-.006L10.56 1.5zM9.504.43a1.516 1.516 0 0 1 2.437 1.713L10.415 5.5h2.123c1.57 0 2.346 1.909 1.22 3.004l-7.34 7.142a1.25 1.25 0 0 1-.871.354h-.302a1.25 1.25 0 0 1-1.157-1.723L5.633 10.5H3.462c-1.57 0-2.346-1.909-1.22-3.004L9.503.429z"/></svg>');--md-admonition-icon--bug:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M4.72.22a.75.75 0 0 1 1.06 0l1 .999a3.492 3.492 0 0 1 2.441 0l.999-1a.75.75 0 1 1 1.06 1.061l-.775.776c.616.63.995 1.493.995 2.444v.327c0 .1-.009.197-.025.292.408.14.764.392 1.029.722l1.968-.787a.75.75 0 0 1 .556 1.392L13 7.258V9h2.25a.75.75 0 0 1 0 1.5H13v.5c0 .409-.049.806-.141 1.186l2.17.868a.75.75 0 0 1-.557 1.392l-2.184-.873A4.997 4.997 0 0 1 8 16a4.997 4.997 0 0 1-4.288-2.427l-2.183.873a.75.75 0 0 1-.558-1.392l2.17-.868A5.013 5.013 0 0 1 3 11v-.5H.75a.75.75 0 0 1 0-1.5H3V7.258L.971 6.446a.75.75 0 0 1 .558-1.392l1.967.787c.265-.33.62-.583 1.03-.722a1.684 1.684 0 0 1-.026-.292V4.5c0-.951.38-1.814.995-2.444L4.72 1.28a.75.75 0 0 1 0-1.06zM6.173 5h3.654A.173.173 0 0 0 10 4.827V4.5a2 2 0 1 0-4 0v.327c0 .096.077.173.173.173zM5.25 6.5a.75.75 0 0 0-.75.75V11a3.5 3.5 0 1 0 7 0V7.25a.75.75 0 0 0-.75-.75h-5.5z"/></svg>');--md-admonition-icon--example:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M5 5.782V2.5h-.25a.75.75 0 0 1 0-1.5h6.5a.75.75 0 0 1 0 1.5H11v3.282l3.666 5.76C15.619 13.04 14.543 15 12.767 15H3.233c-1.776 0-2.852-1.96-1.899-3.458L5 5.782zM9.5 2.5h-3V6a.75.75 0 0 1-.117.403L4.73 9h6.54L9.617 6.403A.75.75 0 0 1 9.5 6V2.5zm-6.9 9.847L3.775 10.5h8.45l1.175 1.847a.75.75 0 0 1-.633 1.153H3.233a.75.75 0 0 1-.633-1.153z"/></svg>');--md-admonition-icon--quote:url('data:image/svg+xml;charset=utf-8,<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 16 16"><path fill-rule="evenodd" d="M1.75 2.5a.75.75 0 0 0 0 1.5h10.5a.75.75 0 0 0 0-1.5H1.75zm4 5a.75.75 0 0 0 0 1.5h8.5a.75.75 0 0 0 0-1.5h-8.5zm0 5a.75.75 0 0 0 0 1.5h8.5a.75.75 0 0 0 0-1.5h-8.5zM2.5 7.75a.75.75 0 0 0-1.5 0v6a.75.75 0 0 0 1.5 0v-6z"/></svg>');}</style>
<link crossorigin="" href="https://fonts.gstatic.com" rel="preconnect"/>
<link href="https://fonts.googleapis.com/css?family=Roboto:300,300i,400,400i,700,700i%7CRoboto+Mono:400,400i,700,700i&amp;display=fallback" rel="stylesheet"/>
<style>:root{--md-text-font:"Roboto";--md-code-font:"Roboto Mono"}</style>
<script>__md_scope=new URL("../../..",location),__md_hash=e=>[...e].reduce((e,_)=>(e<<5)-e+_.charCodeAt(0),0),__md_get=(e,_=localStorage,t=__md_scope)=>JSON.parse(_.getItem(t.pathname+"."+e)),__md_set=(e,_,t=localStorage,a=__md_scope)=>{try{t.setItem(a.pathname+"."+e,JSON.stringify(_))}catch(e){}}</script>
<link href="../../../assets/stylesheets/glightbox.min.css" rel="stylesheet"/><style>
            html.glightbox-open { overflow: initial; height: 100%; }
            .gdesc-inner { font-size: 0.75rem; }
            .gslide-title { margin-top: 0px; user-select: text; }
            .gslide-desc { color: #666; user-select: text; }
            .gslide-image img { background: white; }
            
                .gscrollbar-fixer { padding-right: 15px; }
                </style><script src="../../../assets/javascripts/glightbox.min.js"></script></head>
<body data-md-color-accent="indigo" data-md-color-primary="white" data-md-color-scheme="default" dir="ltr">
<script>var palette=__md_get("__palette");if(palette&&"object"==typeof palette.color)for(var key of Object.keys(palette.color))document.body.setAttribute("data-md-color-"+key,palette.color[key])</script>
<input autocomplete="off" class="md-toggle" data-md-toggle="drawer" id="__drawer" type="checkbox"/>
<input autocomplete="off" class="md-toggle" data-md-toggle="search" id="__search" type="checkbox"/>
<label class="md-overlay" for="__drawer"></label>
<div data-md-component="skip">
<a class="md-skip" href="#_1">
          跳转至
        </a>
</div>
<div data-md-component="announce">
</div>
<header class="md-header" data-md-component="header">
<nav aria-label="页眉" class="md-header__inner md-grid">
<a aria-label="玉子的笔记本" class="md-header__button md-logo" data-md-component="logo" href="../../.." title="玉子的笔记本">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54Z"></path></svg>
</a>
<label class="md-header__button md-icon" for="__drawer">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M3 6h18v2H3V6m0 5h18v2H3v-2m0 5h18v2H3v-2Z"></path></svg>
</label>
<div class="md-header__title" data-md-component="header-title">
<div class="md-header__ellipsis">
<div class="md-header__topic">
<span class="md-ellipsis">
            玉子的笔记本
          </span>
</div>
<div class="md-header__topic" data-md-component="header-topic">
<span class="md-ellipsis">
            
              队列
            
          </span>
</div>
</div>
</div>
<form class="md-header__option" data-md-component="palette">
<input aria-label="Switch to dark mode" class="md-option" data-md-color-accent="indigo" data-md-color-media="(prefers-color-scheme: light)" data-md-color-primary="white" data-md-color-scheme="default" id="__palette_1" name="__palette" type="radio"/>
<label class="md-header__button md-icon" for="__palette_2" hidden="" title="Switch to dark mode">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 8a4 4 0 0 0-4 4 4 4 0 0 0 4 4 4 4 0 0 0 4-4 4 4 0 0 0-4-4m0 10a6 6 0 0 1-6-6 6 6 0 0 1 6-6 6 6 0 0 1 6 6 6 6 0 0 1-6 6m8-9.31V4h-4.69L12 .69 8.69 4H4v4.69L.69 12 4 15.31V20h4.69L12 23.31 15.31 20H20v-4.69L23.31 12 20 8.69Z"></path></svg>
</label>
<input aria-label="Switch to light mode" class="md-option" data-md-color-accent="indigo" data-md-color-media="(prefers-color-scheme: dark)" data-md-color-primary="black" data-md-color-scheme="slate" id="__palette_2" name="__palette" type="radio"/>
<label class="md-header__button md-icon" for="__palette_1" hidden="" title="Switch to light mode">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 18c-.89 0-1.74-.2-2.5-.55C11.56 16.5 13 14.42 13 12c0-2.42-1.44-4.5-3.5-5.45C10.26 6.2 11.11 6 12 6a6 6 0 0 1 6 6 6 6 0 0 1-6 6m8-9.31V4h-4.69L12 .69 8.69 4H4v4.69L.69 12 4 15.31V20h4.69L12 23.31 15.31 20H20v-4.69L23.31 12 20 8.69Z"></path></svg>
</label>
</form>
<div class="md-header__source">
<a class="md-source" data-md-component="source" href="https://gitee.com/huaxv/my_mkdocs.git" title="前往仓库">
<div class="md-source__icon md-icon">
<svg viewbox="0 0 448 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc.--><path d="M439.55 236.05 244 40.45a28.87 28.87 0 0 0-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 0 1-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 0 0 0 40.81l195.61 195.6a28.86 28.86 0 0 0 40.8 0l194.69-194.69a28.86 28.86 0 0 0 0-40.81z"></path></svg>
</div>
<div class="md-source__repository">
    花续情愫缘 / my_mkdocs
  </div>
</a>
</div>
</nav>
</header>
<div class="md-container" data-md-component="container">
<nav aria-label="标签" class="md-tabs" data-md-component="tabs">
<div class="md-tabs__inner md-grid">
<ul class="md-tabs__list">
<li class="md-tabs__item">
<a class="md-tabs__link" href="../../..">
        简介
      </a>
</li>
<li class="md-tabs__item">
<a class="md-tabs__link md-tabs__link--active" href="../%E5%8D%95%E9%93%BE%E8%A1%A8/">
        数据结构
      </a>
</li>
</ul>
</div>
</nav>
<main class="md-main" data-md-component="main">
<div class="md-main__inner md-grid">
<div class="md-sidebar md-sidebar--primary" data-md-component="sidebar" data-md-type="navigation">
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav aria-label="导航栏" class="md-nav md-nav--primary md-nav--lifted" data-md-level="0">
<label class="md-nav__title" for="__drawer">
<a aria-label="玉子的笔记本" class="md-nav__button md-logo" data-md-component="logo" href="../../.." title="玉子的笔记本">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 8a3 3 0 0 0 3-3 3 3 0 0 0-3-3 3 3 0 0 0-3 3 3 3 0 0 0 3 3m0 3.54C9.64 9.35 6.5 8 3 8v11c3.5 0 6.64 1.35 9 3.54 2.36-2.19 5.5-3.54 9-3.54V8c-3.5 0-6.64 1.35-9 3.54Z"></path></svg>
</a>
    玉子的笔记本
  </label>
<div class="md-nav__source">
<a class="md-source" data-md-component="source" href="https://gitee.com/huaxv/my_mkdocs.git" title="前往仓库">
<div class="md-source__icon md-icon">
<svg viewbox="0 0 448 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 6.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2022 Fonticons, Inc.--><path d="M439.55 236.05 244 40.45a28.87 28.87 0 0 0-40.81 0l-40.66 40.63 51.52 51.52c27.06-9.14 52.68 16.77 43.39 43.68l49.66 49.66c34.23-11.8 61.18 31 35.47 56.69-26.49 26.49-70.21-2.87-56-37.34L240.22 199v121.85c25.3 12.54 22.26 41.85 9.08 55a34.34 34.34 0 0 1-48.55 0c-17.57-17.6-11.07-46.91 11.25-56v-123c-20.8-8.51-24.6-30.74-18.64-45L142.57 101 8.45 235.14a28.86 28.86 0 0 0 0 40.81l195.61 195.6a28.86 28.86 0 0 0 40.8 0l194.69-194.69a28.86 28.86 0 0 0 0-40.81z"></path></svg>
</div>
<div class="md-source__repository">
    花续情愫缘 / my_mkdocs
  </div>
</a>
</div>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item md-nav__item--nested">
<input checked="" class="md-nav__toggle md-toggle md-toggle--indeterminate" data-md-toggle="__nav_1" id="__nav_1" type="checkbox"/>
<label class="md-nav__link" for="__nav_1">
          简介
          <span class="md-nav__icon md-icon"></span>
</label>
<nav aria-label="简介" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_1">
<span class="md-nav__icon md-icon"></span>
          简介
        </label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../../..">
        简介
      </a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item md-nav__item--active md-nav__item--nested">
<input checked="" class="md-nav__toggle md-toggle" data-md-toggle="__nav_2" id="__nav_2" type="checkbox"/>
<label class="md-nav__link" for="__nav_2">
          数据结构
          <span class="md-nav__icon md-icon"></span>
</label>
<nav aria-label="数据结构" class="md-nav" data-md-level="1">
<label class="md-nav__title" for="__nav_2">
<span class="md-nav__icon md-icon"></span>
          数据结构
        </label>
<ul class="md-nav__list" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%8D%95%E9%93%BE%E8%A1%A8/">
        单链表
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E6%A0%88/">
        栈
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/">
        后缀表达式
      </a>
</li>
<li class="md-nav__item md-nav__item--active">
<input class="md-nav__toggle md-toggle" data-md-toggle="toc" id="__toc" type="checkbox"/>
<label class="md-nav__link md-nav__link--active" for="__toc">
          队列
          <span class="md-nav__icon md-icon"></span>
</label>
<a class="md-nav__link md-nav__link--active" href="./">
        队列
      </a>
<nav aria-label="目录" class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
      目录
    </label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="#_2">
    数组版：循环队列
  </a>
<nav aria-label="数组版：循环队列" class="md-nav">
<ul class="md-nav__list">
<li class="md-nav__item">
<a class="md-nav__link" href="#init">
    init 初始化
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#empty">
    empty
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#size">
    size
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#full">
    full
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#push">
    push
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#pop">
    pop
  </a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#_3">
    结构体版
  </a>
<nav aria-label="结构体版" class="md-nav">
<ul class="md-nav__list">
<li class="md-nav__item">
<a class="md-nav__link" href="#_4">
    结构体定义
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#init_1">
    init 初始化
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#empty_1">
    empty 判断队列是否为空
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#size_1">
    size 队列长度
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#push_1">
    push 尾进
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#popfront">
    pop、front 头出
  </a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97/">
        双端队列
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E4%BA%8C%E5%8F%89%E5%A0%86/">
        二叉堆
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E9%85%8D%E5%AF%B9%E5%A0%86/">
        配对堆 (可并堆)
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%B7%A6%E5%81%8F%E6%A0%91/">
        左偏树 (可并堆)
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%B9%B6%E6%9F%A5%E9%9B%86/">
        并查集
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%88%86%E5%9D%97%E6%80%9D%E6%83%B3/">
        分块思想
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%8D%95%E8%B0%83%E6%A0%88/">
        单调栈
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97/">
        单调队列
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../ST%20%E8%A1%A8/">
        ST 表
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/">
        树状数组
      </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="../%E9%9C%8D%E5%A4%AB%E6%9B%BC%E6%A0%91/">
        霍夫曼树
      </a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-sidebar md-sidebar--secondary" data-md-component="sidebar" data-md-type="toc">
<div class="md-sidebar__scrollwrap">
<div class="md-sidebar__inner">
<nav aria-label="目录" class="md-nav md-nav--secondary">
<label class="md-nav__title" for="__toc">
<span class="md-nav__icon md-icon"></span>
      目录
    </label>
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
<li class="md-nav__item">
<a class="md-nav__link" href="#_2">
    数组版：循环队列
  </a>
<nav aria-label="数组版：循环队列" class="md-nav">
<ul class="md-nav__list">
<li class="md-nav__item">
<a class="md-nav__link" href="#init">
    init 初始化
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#empty">
    empty
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#size">
    size
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#full">
    full
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#push">
    push
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#pop">
    pop
  </a>
</li>
</ul>
</nav>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#_3">
    结构体版
  </a>
<nav aria-label="结构体版" class="md-nav">
<ul class="md-nav__list">
<li class="md-nav__item">
<a class="md-nav__link" href="#_4">
    结构体定义
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#init_1">
    init 初始化
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#empty_1">
    empty 判断队列是否为空
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#size_1">
    size 队列长度
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#push_1">
    push 尾进
  </a>
</li>
<li class="md-nav__item">
<a class="md-nav__link" href="#popfront">
    pop、front 头出
  </a>
</li>
</ul>
</nav>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="md-content" data-md-component="content">
<article class="md-content__inner md-typeset">
<h1 id="_1">队列</h1>
<p>队列: 是一种「先进先出」的数据结构。</p>
<p>尾进，头出</p>
<h2 id="_2">数组版：循环队列</h2>
<p>给定一个数组 <code>q[N]</code> ，规定 <code>q[0]</code> 指向队头，<code>q[1]</code> 指向队尾，并且规定队尾不存放数据，可存放数据的区间为：<span class="arithmatex">\([2, N - 1]\)</span></p>
<p><a class="glightbox" data-desc-position="bottom" data-description="" data-height="auto" data-title="" data-width="100%" href="../../../img/%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97%E7%A4%BA%E6%84%8F%E5%9B%BE.png"><img alt="循环队列示意图" src="../../../img/%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97%E7%A4%BA%E6%84%8F%E5%9B%BE.png" width="40%"/></a></p>
<h3 id="init">init 初始化</h3>
<p>让 <code>q[0]</code> 和 <code>q[1]</code> 同时指向 <span class="arithmatex">\([2, N - 1]\)</span> 的任意一个位置就行，我这里指向 2</p>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-0-1" id="__codelineno-0-1" name="__codelineno-0-1"></a><span class="k">const</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">(</span><span class="mf">1e5</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">10</span><span class="p">);</span><span class="w"></span>
<a href="#__codelineno-0-2" id="__codelineno-0-2" name="__codelineno-0-2"></a><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span><span class="w"> </span><span class="c1">// 尾进头出，规定 q[0] 代表队头，q[1] 代表队尾</span>
<a href="#__codelineno-0-3" id="__codelineno-0-3" name="__codelineno-0-3"></a>
<a href="#__codelineno-0-4" id="__codelineno-0-4" name="__codelineno-0-4"></a><span class="c1">// 初始化队列</span>
<a href="#__codelineno-0-5" id="__codelineno-0-5" name="__codelineno-0-5"></a><span class="kt">void</span><span class="w"> </span><span class="nf">init</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a href="#__codelineno-0-6" id="__codelineno-0-6" name="__codelineno-0-6"></a><span class="p">{</span><span class="w"> </span>
<a href="#__codelineno-0-7" id="__codelineno-0-7" name="__codelineno-0-7"></a><span class="w">    </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-0-8" id="__codelineno-0-8" name="__codelineno-0-8"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="empty">empty</h3>
<p>如果 <code>q[0] == q[1]</code> ，说明队列为空：</p>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-1-1" id="__codelineno-1-1" name="__codelineno-1-1"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">empty</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a href="#__codelineno-1-2" id="__codelineno-1-2" name="__codelineno-1-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-1-3" id="__codelineno-1-3" name="__codelineno-1-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">];</span><span class="w"></span>
<a href="#__codelineno-1-4" id="__codelineno-1-4" name="__codelineno-1-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="size">size</h3>
<p>如果 <code>q[0] &lt;= q[1]</code>， 队列长度为：<code>q[1] - q[0]</code>；</p>
<p>如果 <code>q[0] &gt; q[1]</code> ，队列长度为：<code>q[1] - 2 + N - q[0] = q[1] - q[0] + N - 2</code></p>
<p>联立上述两种情况：<code>size = (q[1] - q[0] + N - 2) % (N - 2)</code></p>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-2-1" id="__codelineno-2-1" name="__codelineno-2-1"></a><span class="kt">int</span><span class="w"> </span><span class="nf">size</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a href="#__codelineno-2-2" id="__codelineno-2-2" name="__codelineno-2-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-2-3" id="__codelineno-2-3" name="__codelineno-2-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">);</span><span class="w"></span>
<a href="#__codelineno-2-4" id="__codelineno-2-4" name="__codelineno-2-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="full">full</h3>
<p>如果 <code>size == N - 3</code>，说明此时已满</p>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-3-1" id="__codelineno-3-1" name="__codelineno-3-1"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">full</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a href="#__codelineno-3-2" id="__codelineno-3-2" name="__codelineno-3-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-3-3" id="__codelineno-3-3" name="__codelineno-3-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">size</span><span class="p">(</span><span class="n">q</span><span class="p">)</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">3</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-3-4" id="__codelineno-3-4" name="__codelineno-3-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="push">push</h3>
<p>执行 <code>q[q[1]] = x</code> ，<code>q[1] ++</code> 右移</p>
<p>右移时，如果 <code>q[1] == N</code> 就要让 <code>q[1] = 2</code>，说到底，<code>q[1]</code> 的取值范围为：<span class="arithmatex">\([2, N - 1] = [0, N - 3] + 2\)</span>，所以 </p>
<blockquote>
<p><code>q[1] = (q[1] - 2 + 1) % (N - 2) + 2 = (q[1] - 1) % (N - 2) + 2</code></p>
</blockquote>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-4-1" id="__codelineno-4-1" name="__codelineno-4-1"></a><span class="kt">void</span><span class="w"> </span><span class="nf">push</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[],</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
<a href="#__codelineno-4-2" id="__codelineno-4-2" name="__codelineno-4-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-4-3" id="__codelineno-4-3" name="__codelineno-4-3"></a><span class="w">    </span><span class="n">q</span><span class="p">[</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span><span class="p">;</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-4-4" id="__codelineno-4-4" name="__codelineno-4-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="pop">pop</h3>
<p>同理，删除操作，先记录下 <code>q[0]</code> 的值，再执行和上述右移一样的操作。</p>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-5-1" id="__codelineno-5-1" name="__codelineno-5-1"></a><span class="kt">int</span><span class="w"> </span><span class="nf">pop</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a href="#__codelineno-5-2" id="__codelineno-5-2" name="__codelineno-5-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-5-3" id="__codelineno-5-3" name="__codelineno-5-3"></a><span class="w">    </span><span class="kt">int</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]];</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-5-4" id="__codelineno-5-4" name="__codelineno-5-4"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">t</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-5-5" id="__codelineno-5-5" name="__codelineno-5-5"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<details class="note">
<summary>代码汇总</summary>
<p><a href="https://www.acwing.com/problem/content/831/">模拟队列</a></p>
<div class="highlight"><table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><span></span><span class="normal"><a href="#__codelineno-6-1"> 1</a></span>
<span class="normal"><a href="#__codelineno-6-2"> 2</a></span>
<span class="normal"><a href="#__codelineno-6-3"> 3</a></span>
<span class="normal"><a href="#__codelineno-6-4"> 4</a></span>
<span class="normal"><a href="#__codelineno-6-5"> 5</a></span>
<span class="normal"><a href="#__codelineno-6-6"> 6</a></span>
<span class="normal"><a href="#__codelineno-6-7"> 7</a></span>
<span class="normal"><a href="#__codelineno-6-8"> 8</a></span>
<span class="normal"><a href="#__codelineno-6-9"> 9</a></span>
<span class="normal"><a href="#__codelineno-6-10">10</a></span>
<span class="normal"><a href="#__codelineno-6-11">11</a></span>
<span class="normal"><a href="#__codelineno-6-12">12</a></span>
<span class="normal"><a href="#__codelineno-6-13">13</a></span>
<span class="normal"><a href="#__codelineno-6-14">14</a></span>
<span class="normal"><a href="#__codelineno-6-15">15</a></span>
<span class="normal"><a href="#__codelineno-6-16">16</a></span>
<span class="normal"><a href="#__codelineno-6-17">17</a></span>
<span class="normal"><a href="#__codelineno-6-18">18</a></span>
<span class="normal"><a href="#__codelineno-6-19">19</a></span>
<span class="normal"><a href="#__codelineno-6-20">20</a></span>
<span class="normal"><a href="#__codelineno-6-21">21</a></span>
<span class="normal"><a href="#__codelineno-6-22">22</a></span>
<span class="normal"><a href="#__codelineno-6-23">23</a></span>
<span class="normal"><a href="#__codelineno-6-24">24</a></span>
<span class="normal"><a href="#__codelineno-6-25">25</a></span>
<span class="normal"><a href="#__codelineno-6-26">26</a></span>
<span class="normal"><a href="#__codelineno-6-27">27</a></span>
<span class="normal"><a href="#__codelineno-6-28">28</a></span>
<span class="normal"><a href="#__codelineno-6-29">29</a></span>
<span class="normal"><a href="#__codelineno-6-30">30</a></span>
<span class="normal"><a href="#__codelineno-6-31">31</a></span>
<span class="normal"><a href="#__codelineno-6-32">32</a></span>
<span class="normal"><a href="#__codelineno-6-33">33</a></span>
<span class="normal"><a href="#__codelineno-6-34">34</a></span>
<span class="normal"><a href="#__codelineno-6-35">35</a></span>
<span class="normal"><a href="#__codelineno-6-36">36</a></span>
<span class="normal"><a href="#__codelineno-6-37">37</a></span>
<span class="normal"><a href="#__codelineno-6-38">38</a></span>
<span class="normal"><a href="#__codelineno-6-39">39</a></span>
<span class="normal"><a href="#__codelineno-6-40">40</a></span>
<span class="normal"><a href="#__codelineno-6-41">41</a></span>
<span class="normal"><a href="#__codelineno-6-42">42</a></span>
<span class="normal"><a href="#__codelineno-6-43">43</a></span>
<span class="normal"><a href="#__codelineno-6-44">44</a></span>
<span class="normal"><a href="#__codelineno-6-45">45</a></span>
<span class="normal"><a href="#__codelineno-6-46">46</a></span>
<span class="normal"><a href="#__codelineno-6-47">47</a></span>
<span class="normal"><a href="#__codelineno-6-48">48</a></span>
<span class="normal"><a href="#__codelineno-6-49">49</a></span></pre></div></td><td class="code"><div><pre><span></span><code><a id="__codelineno-6-1" name="__codelineno-6-1"></a><span class="k">const</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="p">(</span><span class="mf">1e5</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">10</span><span class="p">);</span><span class="w"></span>
<a id="__codelineno-6-2" name="__codelineno-6-2"></a><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="n">N</span><span class="p">];</span><span class="w"> </span><span class="c1">// 尾进头出，规定 q[0] 代表队头，q[1] 代表队尾</span>
<a id="__codelineno-6-3" name="__codelineno-6-3"></a>
<a id="__codelineno-6-4" name="__codelineno-6-4"></a><span class="c1">// 初始化队列</span>
<a id="__codelineno-6-5" name="__codelineno-6-5"></a><span class="kt">void</span><span class="w"> </span><span class="nf">init</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-6" name="__codelineno-6-6"></a><span class="p">{</span><span class="w"> </span>
<a id="__codelineno-6-7" name="__codelineno-6-7"></a><span class="w">    </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a id="__codelineno-6-8" name="__codelineno-6-8"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-9" name="__codelineno-6-9"></a>
<a id="__codelineno-6-10" name="__codelineno-6-10"></a><span class="c1">// 规定 q[0] == q[1] 时，队列为空</span>
<a id="__codelineno-6-11" name="__codelineno-6-11"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">empty</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-12" name="__codelineno-6-12"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-13" name="__codelineno-6-13"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">];</span><span class="w"></span>
<a id="__codelineno-6-14" name="__codelineno-6-14"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-15" name="__codelineno-6-15"></a>
<a id="__codelineno-6-16" name="__codelineno-6-16"></a><span class="c1">// 队列元素个数推导：</span>
<a id="__codelineno-6-17" name="__codelineno-6-17"></a><span class="c1">// 如果 q[0] &lt;= q[1]，则 size = q[1] - q[0]</span>
<a id="__codelineno-6-18" name="__codelineno-6-18"></a><span class="c1">// 如果 q[1] &lt; q[0]，则 size = q[1] - 2 + N - q[0] = q[1] - q[0] + N - 2</span>
<a id="__codelineno-6-19" name="__codelineno-6-19"></a><span class="c1">// 统合上述两种情况：size = (q[1] - q[0] + N - 2) % (N - 2)</span>
<a id="__codelineno-6-20" name="__codelineno-6-20"></a><span class="kt">int</span><span class="w"> </span><span class="nf">size</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-21" name="__codelineno-6-21"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-22" name="__codelineno-6-22"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">);</span><span class="w"></span>
<a id="__codelineno-6-23" name="__codelineno-6-23"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-24" name="__codelineno-6-24"></a>
<a id="__codelineno-6-25" name="__codelineno-6-25"></a><span class="c1">// 判断数组元素是否用完，数组长度为 N ，实际可用空间为：N - 3</span>
<a id="__codelineno-6-26" name="__codelineno-6-26"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">full</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-27" name="__codelineno-6-27"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-28" name="__codelineno-6-28"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">size</span><span class="p">(</span><span class="n">q</span><span class="p">)</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">3</span><span class="p">;</span><span class="w"></span>
<a id="__codelineno-6-29" name="__codelineno-6-29"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-30" name="__codelineno-6-30"></a>
<a id="__codelineno-6-31" name="__codelineno-6-31"></a><span class="c1">// 插入元素，队尾右移，q[1] 的取值范围是 [2, N - 1] = [0, N - 3] + 2</span>
<a id="__codelineno-6-32" name="__codelineno-6-32"></a><span class="c1">// 因此 q[1] = (q[1] - 2 + 1)% (N - 2) + 2 = (q[1] - 1) % (N - 2) + 2</span>
<a id="__codelineno-6-33" name="__codelineno-6-33"></a><span class="kt">void</span><span class="w"> </span><span class="nf">push</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[],</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
<a id="__codelineno-6-34" name="__codelineno-6-34"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-35" name="__codelineno-6-35"></a><span class="w">    </span><span class="n">q</span><span class="p">[</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">x</span><span class="p">;</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a id="__codelineno-6-36" name="__codelineno-6-36"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-37" name="__codelineno-6-37"></a>
<a id="__codelineno-6-38" name="__codelineno-6-38"></a><span class="c1">// 获取队头元素</span>
<a id="__codelineno-6-39" name="__codelineno-6-39"></a><span class="kt">int</span><span class="w"> </span><span class="nf">front</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-40" name="__codelineno-6-40"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-41" name="__codelineno-6-41"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]];</span><span class="w"></span>
<a id="__codelineno-6-42" name="__codelineno-6-42"></a><span class="p">}</span><span class="w"></span>
<a id="__codelineno-6-43" name="__codelineno-6-43"></a>
<a id="__codelineno-6-44" name="__codelineno-6-44"></a><span class="c1">// 删除队头元素并返回，队头右移</span>
<a id="__codelineno-6-45" name="__codelineno-6-45"></a><span class="kt">int</span><span class="w"> </span><span class="nf">pop</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">q</span><span class="p">[])</span><span class="w"></span>
<a id="__codelineno-6-46" name="__codelineno-6-46"></a><span class="p">{</span><span class="w"></span>
<a id="__codelineno-6-47" name="__codelineno-6-47"></a><span class="w">    </span><span class="kt">int</span><span class="w"> </span><span class="n">t</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]];</span><span class="w"> </span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">(</span><span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">1</span><span class="p">)</span><span class="w"> </span><span class="o">%</span><span class="w"> </span><span class="p">(</span><span class="n">N</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="mi">2</span><span class="p">;</span><span class="w"></span>
<a id="__codelineno-6-48" name="__codelineno-6-48"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">t</span><span class="p">;</span><span class="w"></span>
<a id="__codelineno-6-49" name="__codelineno-6-49"></a><span class="p">}</span><span class="w"></span>
</code></pre></div></td></tr></table></div>
</details>
<h2 id="_3">结构体版</h2>
<p>规定头节点存放队列的长度信息，头节点的 next 指针才指向实际的队列</p>
<h3 id="_4">结构体定义</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-7-1" id="__codelineno-7-1" name="__codelineno-7-1"></a><span class="k">struct</span><span class="w"> </span><span class="nc">Node</span><span class="w"></span>
<a href="#__codelineno-7-2" id="__codelineno-7-2" name="__codelineno-7-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-7-3" id="__codelineno-7-3" name="__codelineno-7-3"></a><span class="w">    </span><span class="kt">int</span><span class="w"> </span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-7-4" id="__codelineno-7-4" name="__codelineno-7-4"></a><span class="w">    </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">ne</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-7-5" id="__codelineno-7-5" name="__codelineno-7-5"></a><span class="w">    </span><span class="n">Node</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">val</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">nullptr</span><span class="p">)</span><span class="w"></span>
<a href="#__codelineno-7-6" id="__codelineno-7-6" name="__codelineno-7-6"></a><span class="w">    </span><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-7-7" id="__codelineno-7-7" name="__codelineno-7-7"></a><span class="w">        </span><span class="n">v</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">val</span><span class="p">,</span><span class="w"> </span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">next</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-7-8" id="__codelineno-7-8" name="__codelineno-7-8"></a><span class="w">    </span><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-7-9" id="__codelineno-7-9" name="__codelineno-7-9"></a><span class="p">};</span><span class="w"></span>
</code></pre></div>
<h3 id="init_1">init 初始化</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-8-1" id="__codelineno-8-1" name="__codelineno-8-1"></a><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">head</span><span class="p">,</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">tail</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-8-2" id="__codelineno-8-2" name="__codelineno-8-2"></a>
<a href="#__codelineno-8-3" id="__codelineno-8-3" name="__codelineno-8-3"></a><span class="kt">void</span><span class="w"> </span><span class="nf">init</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-8-4" id="__codelineno-8-4" name="__codelineno-8-4"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-8-5" id="__codelineno-8-5" name="__codelineno-8-5"></a><span class="w">    </span><span class="c1">// 初始时，队列长度为 0，头节点的 v 也是 0</span>
<a href="#__codelineno-8-6" id="__codelineno-8-6" name="__codelineno-8-6"></a><span class="w">    </span><span class="n">head</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">tail</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">new</span><span class="w"> </span><span class="n">Node</span><span class="p">();</span><span class="w"></span>
<a href="#__codelineno-8-7" id="__codelineno-8-7" name="__codelineno-8-7"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="empty_1">empty 判断队列是否为空</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-9-1" id="__codelineno-9-1" name="__codelineno-9-1"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">empty</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-9-2" id="__codelineno-9-2" name="__codelineno-9-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-9-3" id="__codelineno-9-3" name="__codelineno-9-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">tail</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-9-4" id="__codelineno-9-4" name="__codelineno-9-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="size_1">size 队列长度</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-10-1" id="__codelineno-10-1" name="__codelineno-10-1"></a><span class="kt">int</span><span class="w"> </span><span class="nf">size</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-10-2" id="__codelineno-10-2" name="__codelineno-10-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-10-3" id="__codelineno-10-3" name="__codelineno-10-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-10-4" id="__codelineno-10-4" name="__codelineno-10-4"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="push_1">push 尾进</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-11-1" id="__codelineno-11-1" name="__codelineno-11-1"></a><span class="kt">void</span><span class="w"> </span><span class="nf">push</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
<a href="#__codelineno-11-2" id="__codelineno-11-2" name="__codelineno-11-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-11-3" id="__codelineno-11-3" name="__codelineno-11-3"></a><span class="w">    </span><span class="n">tail</span><span class="o">-&gt;</span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">new</span><span class="w"> </span><span class="n">Node</span><span class="p">(</span><span class="n">x</span><span class="p">);</span><span class="w"> </span><span class="n">tail</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">tail</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-11-4" id="__codelineno-11-4" name="__codelineno-11-4"></a><span class="w">    </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="w"> </span><span class="o">++</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-11-5" id="__codelineno-11-5" name="__codelineno-11-5"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<h3 id="popfront">pop、front 头出</h3>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-12-1" id="__codelineno-12-1" name="__codelineno-12-1"></a><span class="kt">int</span><span class="w"> </span><span class="nf">front</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-12-2" id="__codelineno-12-2" name="__codelineno-12-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-12-3" id="__codelineno-12-3" name="__codelineno-12-3"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="o">-&gt;</span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-12-4" id="__codelineno-12-4" name="__codelineno-12-4"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-12-5" id="__codelineno-12-5" name="__codelineno-12-5"></a>
<a href="#__codelineno-12-6" id="__codelineno-12-6" name="__codelineno-12-6"></a><span class="kt">void</span><span class="w"> </span><span class="nf">pop</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-12-7" id="__codelineno-12-7" name="__codelineno-12-7"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-12-8" id="__codelineno-12-8" name="__codelineno-12-8"></a><span class="w">    </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">p</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"> </span><span class="k">delete</span><span class="w"> </span><span class="n">p</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-12-9" id="__codelineno-12-9" name="__codelineno-12-9"></a><span class="w">    </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="w"> </span><span class="o">--</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-12-10" id="__codelineno-12-10" name="__codelineno-12-10"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
<details class="note">
<summary>代码汇总</summary>
<div class="highlight"><pre><span></span><code><a href="#__codelineno-13-1" id="__codelineno-13-1" name="__codelineno-13-1"></a><span class="k">struct</span><span class="w"> </span><span class="nc">Node</span><span class="w"></span>
<a href="#__codelineno-13-2" id="__codelineno-13-2" name="__codelineno-13-2"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-3" id="__codelineno-13-3" name="__codelineno-13-3"></a><span class="w">    </span><span class="kt">int</span><span class="w"> </span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-4" id="__codelineno-13-4" name="__codelineno-13-4"></a><span class="w">    </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">ne</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-5" id="__codelineno-13-5" name="__codelineno-13-5"></a><span class="w">    </span><span class="n">Node</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">val</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">next</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">nullptr</span><span class="p">)</span><span class="w"></span>
<a href="#__codelineno-13-6" id="__codelineno-13-6" name="__codelineno-13-6"></a><span class="w">    </span><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-7" id="__codelineno-13-7" name="__codelineno-13-7"></a><span class="w">        </span><span class="n">v</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">val</span><span class="p">,</span><span class="w"> </span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">next</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-8" id="__codelineno-13-8" name="__codelineno-13-8"></a><span class="w">    </span><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-9" id="__codelineno-13-9" name="__codelineno-13-9"></a><span class="p">};</span><span class="w"></span>
<a href="#__codelineno-13-10" id="__codelineno-13-10" name="__codelineno-13-10"></a>
<a href="#__codelineno-13-11" id="__codelineno-13-11" name="__codelineno-13-11"></a><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">head</span><span class="p">,</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="n">tail</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-12" id="__codelineno-13-12" name="__codelineno-13-12"></a>
<a href="#__codelineno-13-13" id="__codelineno-13-13" name="__codelineno-13-13"></a><span class="kt">void</span><span class="w"> </span><span class="nf">init</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-13-14" id="__codelineno-13-14" name="__codelineno-13-14"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-15" id="__codelineno-13-15" name="__codelineno-13-15"></a><span class="w">    </span><span class="c1">// 初始时，队列长度为 0，头节点的 v 也是 0</span>
<a href="#__codelineno-13-16" id="__codelineno-13-16" name="__codelineno-13-16"></a><span class="w">    </span><span class="n">head</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">tail</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">new</span><span class="w"> </span><span class="n">Node</span><span class="p">();</span><span class="w"></span>
<a href="#__codelineno-13-17" id="__codelineno-13-17" name="__codelineno-13-17"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-18" id="__codelineno-13-18" name="__codelineno-13-18"></a>
<a href="#__codelineno-13-19" id="__codelineno-13-19" name="__codelineno-13-19"></a><span class="kt">bool</span><span class="w"> </span><span class="nf">empty</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-13-20" id="__codelineno-13-20" name="__codelineno-13-20"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-21" id="__codelineno-13-21" name="__codelineno-13-21"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="n">tail</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-22" id="__codelineno-13-22" name="__codelineno-13-22"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-23" id="__codelineno-13-23" name="__codelineno-13-23"></a>
<a href="#__codelineno-13-24" id="__codelineno-13-24" name="__codelineno-13-24"></a><span class="kt">int</span><span class="w"> </span><span class="nf">size</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-13-25" id="__codelineno-13-25" name="__codelineno-13-25"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-26" id="__codelineno-13-26" name="__codelineno-13-26"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-27" id="__codelineno-13-27" name="__codelineno-13-27"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-28" id="__codelineno-13-28" name="__codelineno-13-28"></a>
<a href="#__codelineno-13-29" id="__codelineno-13-29" name="__codelineno-13-29"></a><span class="kt">void</span><span class="w"> </span><span class="nf">push</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">x</span><span class="p">)</span><span class="w"></span>
<a href="#__codelineno-13-30" id="__codelineno-13-30" name="__codelineno-13-30"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-31" id="__codelineno-13-31" name="__codelineno-13-31"></a><span class="w">    </span><span class="n">tail</span><span class="o">-&gt;</span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="k">new</span><span class="w"> </span><span class="n">Node</span><span class="p">(</span><span class="n">x</span><span class="p">);</span><span class="w"> </span><span class="n">tail</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">tail</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-32" id="__codelineno-13-32" name="__codelineno-13-32"></a><span class="w">    </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="w"> </span><span class="o">++</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-33" id="__codelineno-13-33" name="__codelineno-13-33"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-34" id="__codelineno-13-34" name="__codelineno-13-34"></a>
<a href="#__codelineno-13-35" id="__codelineno-13-35" name="__codelineno-13-35"></a><span class="kt">int</span><span class="w"> </span><span class="nf">front</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-13-36" id="__codelineno-13-36" name="__codelineno-13-36"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-37" id="__codelineno-13-37" name="__codelineno-13-37"></a><span class="w">    </span><span class="k">return</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="o">-&gt;</span><span class="n">v</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-38" id="__codelineno-13-38" name="__codelineno-13-38"></a><span class="p">}</span><span class="w"></span>
<a href="#__codelineno-13-39" id="__codelineno-13-39" name="__codelineno-13-39"></a>
<a href="#__codelineno-13-40" id="__codelineno-13-40" name="__codelineno-13-40"></a><span class="kt">void</span><span class="w"> </span><span class="nf">pop</span><span class="p">()</span><span class="w"></span>
<a href="#__codelineno-13-41" id="__codelineno-13-41" name="__codelineno-13-41"></a><span class="p">{</span><span class="w"></span>
<a href="#__codelineno-13-42" id="__codelineno-13-42" name="__codelineno-13-42"></a><span class="w">    </span><span class="n">Node</span><span class="o">*</span><span class="w"> </span><span class="n">p</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"> </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">ne</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">p</span><span class="o">-&gt;</span><span class="n">ne</span><span class="p">;</span><span class="w"> </span><span class="k">delete</span><span class="w"> </span><span class="n">p</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-43" id="__codelineno-13-43" name="__codelineno-13-43"></a><span class="w">    </span><span class="n">head</span><span class="o">-&gt;</span><span class="n">v</span><span class="w"> </span><span class="o">--</span><span class="p">;</span><span class="w"></span>
<a href="#__codelineno-13-44" id="__codelineno-13-44" name="__codelineno-13-44"></a><span class="p">}</span><span class="w"></span>
</code></pre></div>
</details>
</article>
</div>
<script>var tabs=__md_get("__tabs");if(Array.isArray(tabs))e:for(var set of document.querySelectorAll(".tabbed-set")){var tab,labels=set.querySelector(".tabbed-labels");for(tab of tabs)for(var label of labels.getElementsByTagName("label"))if(label.innerText.trim()===tab){var input=document.getElementById(label.htmlFor);input.checked=!0;continue e}}</script>
</div>
<a class="md-top md-icon" data-md-component="top" hidden="" href="#">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M13 20h-2V8l-5.5 5.5-1.42-1.42L12 4.16l7.92 7.92-1.42 1.42L13 8v12Z"></path></svg>
            回到页面顶部
          </a>
</main>
<footer class="md-footer">
<nav aria-label="页脚" class="md-footer__inner md-grid">
<a aria-label="上一页: 后缀表达式" class="md-footer__link md-footer__link--prev" href="../%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F/" rel="prev">
<div class="md-footer__button md-icon">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M20 11v2H8l5.5 5.5-1.42 1.42L4.16 12l7.92-7.92L13.5 5.5 8 11h12Z"></path></svg>
</div>
<div class="md-footer__title">
<div class="md-ellipsis">
<span class="md-footer__direction">
                上一页
              </span>
              后缀表达式
            </div>
</div>
</a>
<a aria-label="下一页: 双端队列" class="md-footer__link md-footer__link--next" href="../%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97/" rel="next">
<div class="md-footer__title">
<div class="md-ellipsis">
<span class="md-footer__direction">
                下一页
              </span>
              双端队列
            </div>
</div>
<div class="md-footer__button md-icon">
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M4 11v2h12l-5.5 5.5 1.42 1.42L19.84 12l-7.92-7.92L10.5 5.5 16 11H4Z"></path></svg>
</div>
</a>
</nav>
<div class="md-footer-meta md-typeset">
<div class="md-footer-meta__inner md-grid">
<div class="md-copyright">
  
  
    Made with
    <a href="https://squidfunk.github.io/mkdocs-material/" rel="noopener" target="_blank">
      Material for MkDocs
    </a>
</div>
</div>
</div>
</footer>
</div>
<div class="md-dialog" data-md-component="dialog">
<div class="md-dialog__inner md-typeset"></div>
</div>
<script id="__config" type="application/json">{"base": "../../..", "features": ["navigation.instant", "navigation.tracking", "navigation.tabs", "navigation.sections", "navigation.expand", "navigation.prune", "toc.follow", "navigation.top", "content.code.annotate", "content.tabs.link"], "search": "../../../assets/javascripts/workers/search.16e2a7d4.min.js", "translations": {"clipboard.copied": "\u5df2\u590d\u5236", "clipboard.copy": "\u590d\u5236", "search.config.lang": "ja", "search.config.pipeline": "trimmer, stemmer", "search.config.separator": "[\\s\\-\uff0c\u3002]+", "search.placeholder": "\u641c\u7d22", "search.result.more.one": "\u5728\u8be5\u9875\u4e0a\u8fd8\u6709 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.more.other": "\u5728\u8be5\u9875\u4e0a\u8fd8\u6709 # \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.none": "\u6ca1\u6709\u627e\u5230\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.one": "\u627e\u5230 1 \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.other": "# \u4e2a\u7b26\u5408\u6761\u4ef6\u7684\u7ed3\u679c", "search.result.placeholder": "\u952e\u5165\u4ee5\u5f00\u59cb\u641c\u7d22", "search.result.term.missing": "\u7f3a\u5c11", "select.version.title": "\u9009\u62e9\u5f53\u524d\u7248\u672c"}}</script>
<script src="../../../assets/javascripts/bundle.d6c3db9e.min.js"></script>
<script src="../../../javascripts/mathjax.js"></script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script>document$.subscribe(() => {const lightbox = GLightbox({"touchNavigation": true, "loop": false, "zoomable": true, "draggable": true, "openEffect": "zoom", "closeEffect": "zoom"});})</script></body>
</html>